/*
LC600.不含连续1的非负整数
https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/
困难  2024.10.01  

解法一：数位DP模板
class Solution
{
public:
    int findIntegers(int n)
    {
        int m = __lg(n);
        vector<array<int, 2>> memo(m + 1, {-1, -1});
        function<int(int, bool, bool)> dfs = [&](int i, bool pre, bool limit)
        {
            if (i < 0)
                return 1;

            if (!limit && memo[i][pre] != -1)
            {
                return memo[i][pre];
            }
            int up = limit ? (n >> i) & 1 : 1;
            int res = dfs(i - 1, false, limit && up == 0);
            if (!pre && up == 1)
            {
                res += dfs(i - 1, true, limit);
            }
            if (!limit)
            {
                memo[i][pre] = res;
            }
            return res;
        };
        return dfs(m, false, true);
    }
};

*/

class Solution {
public:
    int findIntegers(int n) {
        int f[32][2];
        for (int i = 0; i < 32; ++i) {
            f[i][0] = f[i][1] = 0;
        }
        // 当只有一位二进制数时（i = 0）
        // f[0][0]表示二进制数0，只有1种情况，所以为1
        // f[0][1]表示二进制数1，也只有1种情况，所以为1
        f[0][0] = 1;
        f[0][1] = 1;
        // 通过动态规划计算f[i][0]和f[i][1]
        // 对于i > 0的情况
        for (int i = 1; i < 32; ++i) {
            // 如果当前位为0，那么前i - 1位可以是任意满足条件（不存在连续1）的情况
            // 所以f[i][0]等于前一位为0和前一位为1的情况之和
            f[i][0] = f[i - 1][0] + f[i - 1][1];
            // 如果当前位为1，为了保证不存在连续1，前一位必须为0
            // 所以f[i][1]等于前一位为0的情况，即f[i - 1][0]
            f[i][1] = f[i - 1][0];
        }

        int prev = 0;
        int ans = 0;
        int bit = 30;
        // 从最高位开始遍历n的二进制位
        while (bit >= 0) {
            // 获取当前位的值，通过右移bit位然后与1进行与运算
            int cur = (n >> bit) & 1;
            // 如果当前位为1
            if (cur == 1) {
                // 将f[bit][0]加到ans中，因为当前位为1时，后面的位可以是任意以0开头的满足条件的数（即f[bit][0]所表示的数量）
                ans += f[bit][0];
                // 如果前一位（prev）也是1，那么这种情况是不满足条件的（存在连续1）,所以要减去1并跳出循环
                if (prev == 1) {
                    ans--;
                    break;
                }
            }
            // 更新prev为当前位的值cur
            prev = cur;
            bit--;
        }
        // 需要加上0
        return ans + 1;
    }
};